数字配对

Time Limit: 10 Sec Memory Limit: 128 MB

Description

有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。

若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，

那么这两个数字可以配对，并获得 ci×cj 的价值。

一个数字只能参与一次配对，可以不参与配对。

在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。

Input

第一行一个整数 n。

第二行 n 个整数 a1、a2、……、an。

第三行 n 个整数 b1、b2、……、bn。

第四行 n 个整数 c1、c2、……、cn。

Output

一行一个数，最多进行多少次配对

Sample Input

3
　2 4 8
　2 200 7
　-1 -2 1

Sample Output

4

HINT

n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5

Solution

显然是一个费用流，并且这可以是一个二分图，由于 ai/aj 要是质数，那显然可以根据质因子个数的奇偶分类。

然后跑一跑最大费用最大流。判断一下值要>=0即可统计入答案。mmpBearChild查了一个下午错，发现是INF开小了qaq。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
#define next nxt
const int N = 1005;
const int M = 400005;
const int INF = 2147483640;

int n;
int a[N], b[N], c[N];
s64 dist[N];
int vis[N], q[N], pre[N];
int first[M], go[M], next[M], pas[M], from[M], tot;
int pNum[M];
int odd[M],Onum, eve[M],Enum;
int S, T, Ans;
int prime[M], isp[M], p;
s64 Val, w[M];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
    if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
    res=res*10+c-48;
    return res*Q;
}

void Getp(int MaxN)
{
    for(int i=2; i <= MaxN; i++)
    {
        if(!isp[i]) prime[++p] = i;
        for(int j=1; j <= prime[p] && i*prime[j] <= MaxN; j++)
        {
            isp[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

int Factor(int x)
{
    int res = 0;
    while(x != 1)
    {
        for(int i=1; i<=p; i++)
        if(x % prime[i] == 0)
        {
            x /= prime[i];
            res++;
            break;
        }
    }
    return res;
}

int PD(int x, int y)
{
    if(x > y) swap(x, y);
    if(x==0 || y==0 || y%x!=0) return 0;
    x = y / x;
    for(int i=2; i<x; i++)
    if(x % i == 0) return 0;
    return 1;
}

void Add(int u, int v, int flow, s64 z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  pas[tot]=flow;  w[tot]=z;   from[tot]=u;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  pas[tot]=0;     w[tot]=-z;  from[tot]=v;
}

bool Bfs()
{
    for(int i=S; i<=T; i++) dist[i] = -1e18;
    int tou = 0, wei = 1;
    q[1] = S;   vis[S] = 1; dist[S] = 0;
    while(tou < wei)
    {
        int u = q[++tou];
        for(int e=first[u]; e; e=next[e])
        {
            int v=go[e];
            if(dist[v] < dist[u] + w[e] && pas[e])
            {
                dist[v] = dist[u] + w[e];
                pre[v] = e;
                if(!vis[v])
                {
                    q[++wei] = v;
                    vis[v] = 1;
                }
            }
        }
        vis[u] = 0;
    }
    return dist[T] != -1e18;
}

void Deal()
{
    int x = INF;
    for(int e=pre[T]; e; e=pre[from[e]]) x = min(x, pas[e]);
    if(Val + dist[T] * x >= 0)
    {
        for(int e=pre[T]; e; e=pre[from[e]])
        {
            pas[e] -= x;
            pas[((e-1)^1)+1] += x;
        }
        Val += dist[T] * x;
        Ans += x;
        return;
    }
    printf("%lld", Ans - Val / dist[T]);
    exit(0);
}

int main()
{
    Getp(M - 5);
    n = get();
    for(int i=1; i<=n; i++) a[i] = get(), pNum[i] = Factor(a[i]);
    for(int i=1; i<=n; i++) b[i] = get();
    for(int i=1; i<=n; i++) c[i] = get();

    S = 0; T = n+1;
    for(int i=1; i<=n; i++)
    {
        if(pNum[i] & 1) Add(S,i, b[i],0), odd[++Onum] = i;
        else Add(i,T, b[i],0), eve[++Enum] = i;
    }

    for(int i=1; i<=Onum; i++)
    for(int j=1; j<=Enum; j++)
    {
        int x = odd[i], y = eve[j];
        if( PD(a[x], a[y]) )
            Add(x,y, INF,(s64)c[x]*c[y]);
    }

    while(Bfs()) Deal();
    printf("%lld", Ans - Val / dist[T]);
}